def fact(n):
    if n <= 1:
        return 1
    else:
        return n * fact(n - 1)


'''
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120
'''
print(fact(5))


# 尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。
# 这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况
# python没有针对尾递归做优化


def fact2(n):
    return fact_iter(n, 1)


def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)


print(fact2(5))

'''
 汉诺塔的移动可以用递归函数非常简单地实现。
 请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法
# 期待输出:
# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C
move(3, 'A', 'B', 'C')
'''

'''
1.将A上n-1个盘子移到B上（通过C）；
2.将A上剩下的一个盘子移到C上；
3.将n-1个盘子从B移到C上（通过A）。

f(n) = 2^n - 1
f(n) = 2f(n-1) + 1
'''


def move(n, a, b, c):
    """
    汉诺塔移动

    :param n: 起始个数
    :param a: 起始盘
    :param b: 中间盘
    :param c: 目标盘
    :return: 需要移动的次数
    """
    global count
    if n == 1:
        count = count + 1
        print('第' + str(count) + '次:' + a + ' --> ' + c)
    else:
        move(n - 1, a, c, b)  # 将A上n-1个盘子移到B上（通过C）；
        move(1, a, b, c)  # 将A上剩下的一个盘子移到C上
        move(n - 1, b, a, c)  # 将n-1个盘子从B移到C上（通过A）。

count = 0
move(4, 'a', 'b', 'c')
print(count)

'''
找到递归的解决方法：
    你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.
    你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).
如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 
而最小的问题仅需几个有限的步骤就能解决.
'''
